A Unified Framework for Sparse Non-Negative Least Squares using Multiplicative Updates and the Non-Negative Matrix Factorization Problem

摘要

We study the sparse non-negative least squares (S-NNLS) problem. S-NNLSoccurs naturally in a wide variety of applications where an unknown,non-negative quantity must be recovered from linear measurements. We present aunified framework for S-NNLS based on a rectified power exponential scalemixture prior on the sparse codes. We show that the proposed frameworkencompasses a large class of S-NNLS algorithms and provide a computationallyefficient inference procedure based on multiplicative update rules. Such updaterules are convenient for solving large sets of S-NNLS problems simultaneously,which is required in contexts like sparse non-negative matrix factorization(S-NMF). We provide theoretical justification for the proposed approach byshowing that the local minima of the objective function being optimized aresparse and the S-NNLS algorithms presented are guaranteed to converge to a setof stationary points of the objective function. We then extend our framework toS-NMF, showing that our framework leads to many well known S-NMF algorithmsunder specific choices of prior and providing a guarantee that a popularsubclass of the proposed algorithms converges to a set of stationary points ofthe objective function. Finally, we study the performance of the proposedapproaches on synthetic and real-world data.